/**
 * This file is part of System#.
 * 
 * It was taken and adapted from
 * http://www.codeproject.com/Articles/9078/Fraction-class-in-C
 * 
 * Credits go to the original authors
 *  - Syed Mehroz Alam (smehrozalam@yahoo.com) http://www.geocities.com/smehrozalam/
 *  - Marc Brooks
 *  - Jeffrey Sax
 *
 * System# is free software: you can redistribute it and/or modify it under 
 * the terms of the GNU Lesser General Public License (LGPL) as published 
 * by the Free Software Foundation, either version 3 of the License, or (at 
 * your option) any later version.
 *
 * System# is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more 
 * details.
 *
 * You should have received a copy of the GNU General Public License along 
 * with System#. If not, see http://www.gnu.org/licenses/lgpl.html.
 * */

using System;
using System.Runtime.InteropServices;
using System.Globalization;

namespace SystemSharp.DataTypes
{
	/// <summary>
	/// Classes Contained:
	///     Fraction
	///     FractionException
	/// </summary>
	    
	/// Class name: Fraction
	/// Developed by: Syed Mehroz Alam
	/// Email: mailto:smehrozalam@yahoo.com
	/// URL: http://www.geocities.com/smehrozalam/
	/// Changes: Marc C. Brooks  mailto:IDisposable@gmail.com
	///          Jeffery Sax    http://www.extremeoptimization.com
	/// Version: 2.2
	/// 
	/// What's new in version 2.0:
	///     *   Changed Numerator and Denominator from Int32(integer) to Int64(long) for increased range
	///     *   renamed ConvertToString() to (overloaded) ToString()
	///     *   added the capability of detecting/raising overflow exceptions
	///     *   Fixed the bug that very small numbers e.g. 0.00000001 could not be converted to fraction
	///     *   Other minor bugs fixed
	/// 
	/// What's new in version 2.1
	///     *   overloaded user-defined conversions to/from Fractions
	///
	/// What's new in version 2.2 - Marc C. Brooks   mailto:IDisposable@gmail.com
	///     *   less overflows by finding the GCD for Add [Jeffery Sax] and Multiply [Marc C. Brooks]
	///     *   understands and handles NaN, PositiveInfinity, NegativeInfinity just like double [Marc C. Brooks]
	///     *   fixed several uses of int where long was correct [Marc C. Brooks]
	///     *   made value-type (struct) [Jeffery Sax]
	///     *   added ToInt32(), ToInt64() which throw for invalid (NaN, PositiveInfinity, NegativeInfinity) [Marc C. Brooks]
	///     *   removed redundant Value property [Jeffery Sax]
	///     *   added explicit conversion to Int32 and Int64 [Marc C. Brooks]
	///     *   better handling of exceptions [Marc C. Brooks]
	///     *   reorganize code, add XML doc and regions [Marc C. Brooks]
	///     *   proper implementations of Equals [Marc C. Brooks, Jeffery Sax]
	///     *   uses Math.Log(xx,2) and Math.Pow(xx,2) to get the best accuracy possible when converting doubles [Marc C. Brooks, Jeffery Sax]
	///
	/// What's new in version 2.3 - Marc C. Brooks   mailto:IDisposable@gmail.com   01/10/2005
	///     *   fixed double-to-fraction logic to use continued fraction rules to get best possible precistion [bug fix for Syed Mehroz Alam, idea from  Jeffery Sax]
	///     *	added static readonly values for NaN, PositiveInfinity, NegativeInfinity [idea from Jeffery Sax]
	///     *	moved comparisons into an implementation of IComparer [idea from Jeffery Sax]
	///     *	no longer throws for NaN(s) involved in Add, Subtract, Multiply, Divide operations [idea from Jeffery Sax]
	///     *   added static readonly values for Zero, MinValue, MaxValue, Epsilon to better mirror double
	///     *   added IsInfinity to better mirror double.
	///     *   added Modulus and % operators
	///
	/// Properties:
	///     Numerator: Set/Get value for Numerator
	///     Denominator:  Set/Get value for Numerator
	///     [Note: If you Set either Property, the Fraction should be passed to ReduceFraction at some point.]
	/// 
	/// Constructors:
	///     no arguments:   initializes fraction as 0/0 = NaN, so don't do that!
	///     (Numerator, Denominator): initializes fraction with the given numerator and denominator 
	///                               values and reduces
	///     (long): initializes fraction with the given long value
	///     (double):   initializes fraction with the given double value
	///     (string):   initializes fraction with the given string value
	///                 the string can be an in the form of and integer, double or fraction.
	///                 e.g it can be like "123" or "123.321" or "123/456"
	/// 
	/// Public Methods (Description is given with respective methods' definitions)
	///     Fraction ToFraction(long)
	///     Fraction ToFraction(double)
	///     Fraction ToFraction(string)
	///     Int32 ToInt32()
	///     Int64 ToInt64()
	///     double ToDouble()
	///     (override) string ToString()
	///     Fraction Inverse()
	///     Fraction Inverted(long)
	///     Fraction Inverted(double)
	///     ReduceFraction(ref Fraction)
	///     CrossReducePair(ref Fraction, ref Fraction)
	///     (override) Equals(object)
	///     (override) GetHashCode()
	/// 
	/// Overloaded Operators (overloaded for Fractions, long and double)
	///     Unary: -
	///     Binary: +,-,*,/
	///     Relational and Logical Operators: ==,!=,<,>,<=,>= (only == and != for long and doubles)
	/// 
	/// Overloaded user-defined conversions
	///     Implicit:   From long/double/string to Fraction
	///     Explicit:   From Fraction to long/double/string
	/// </summary>
	[Serializable, StructLayout(LayoutKind.Sequential)]
	public struct Fraction : IComparable, IFormattable
	{
		#region Constructors
		/// <summary>
		/// Construct a Fraction from an integral value
		/// </summary>
		/// <param name="wholeNumber">The value (eventual numerator)</param>
		/// <remarks>The denominator will be 1</remarks>
		public Fraction(long wholeNumber)
		{
			if (wholeNumber == long.MinValue)
				wholeNumber++;	// prevent serious issues later..

			m_Numerator = wholeNumber;
			m_Denominator = 1;
			// no reducing required, we're a whole number
		}
	    
		/// <summary>
		/// Construct a Fraction from a floating-point value
		/// </summary>
		/// <param name="floatingPointNumber">The value</param>
		public Fraction(double floatingPointNumber)
		{
			this = ToFraction(floatingPointNumber);
		}
	        
		/// <summary>
		/// Construct a Fraction from a string in any legal format
		/// </summary>
		/// <param name="inValue">A string with a legal fraction input format</param>
		/// <remarks>Will reduce the fraction to smallest possible denominator</remarks>
		/// <see>ToFraction(string strValue)</see>
		public Fraction(string inValue)
		{
			this = ToFraction(inValue);
		}
	        
		/// <summary>
		/// Construct a Fraction from a numerator, denominator pair
		/// </summary>
		/// <param name="numerator">The numerator (top number)</param>
		/// <param name="denominator">The denominator (bottom number)</param>
		/// <remarks>Will reduce the fraction to smallest possible denominator</remarks>
		public Fraction(long numerator, long denominator)
		{
			if (numerator == long.MinValue)
				numerator++;	// prevent serious issues later..

			if (denominator == long.MinValue)
				denominator++;	// prevent serious issues later..

			m_Numerator = numerator;
			m_Denominator = denominator;
			ReduceFraction(ref this);
		}

		/// <summary>
		/// Private constructor to synthesize a Fraction for indeterminates (NaN and infinites)
		/// </summary>
		/// <param name="type">Kind of inderterminate</param>
		private Fraction(Indeterminates type)
		{
			m_Numerator = (long)type;
			m_Denominator = 0;
			// do NOT reduce, we're clean as can be!
		}
		#endregion

		#region Properties
		/// <summary>
		/// The 'top' part of the fraction
		/// </summary>
		/// <example>For 3/4ths, this is the 3</example>
		public long Numerator
		{
			get 
			{
				return m_Numerator;
			}
			set
			{
				m_Numerator = value;
			}
		}

		/// <summary>
		/// The 'bottom' part of the fraction
		/// </summary>
		/// <example>For 3/4ths, this is the 4</example>
		public long Denominator
		{
			get
			{
				return m_Denominator;
			}
			set
			{
				m_Denominator = value;
			}
		}
		#endregion

		#region Expose constants
		public static readonly Fraction NaN = new Fraction(Indeterminates.NaN);
		public static readonly Fraction PositiveInfinity = new Fraction(Indeterminates.PositiveInfinity);
		public static readonly Fraction NegativeInfinity = new Fraction(Indeterminates.NegativeInfinity);
		public static readonly Fraction Zero = new Fraction(0,1);
		public static readonly Fraction Epsilon = new Fraction(1, Int64.MaxValue);
		private static readonly double EpsilonDouble = 1.0 / Int64.MaxValue;
		public static readonly Fraction MaxValue = new Fraction(Int64.MaxValue, 1);
		public static readonly Fraction MinValue = new Fraction(Int64.MinValue, 1);
		#endregion

		#region Explicit conversions
		#region To primitives
		/// <summary>
		/// Get the integral value of the Fraction object as int/Int32
		/// </summary>
		/// <returns>The (approximate) integer value</returns>
		/// <remarks>If the value is not a true integer, the fractional part is discarded
		/// (truncated toward zero). If the valid exceeds the range of an Int32 and exception is thrown.</remarks>
		/// <exception cref="FractionException">Will throw a FractionException for NaN, PositiveInfinity
		/// or NegativeInfinity with the InnerException set to a System.NotFiniteNumberException.</exception>
		/// <exception cref="OverflowException" Will throw a System.OverflowException if the value is too
		/// large or small to be represented as an Int32.</exception>
		public Int32 ToInt32()
		{
			if (this.m_Denominator == 0)
			{
				throw new FractionException(string.Format("Cannot convert {0} to Int32", IndeterminateTypeName(this.m_Numerator)), new System.NotFiniteNumberException());
			}

			long bestGuess = this.m_Numerator / this.m_Denominator;

			if (bestGuess > Int32.MaxValue || bestGuess < Int32.MinValue)
			{
				throw new FractionException("Cannot convert to Int32", new System.OverflowException());
			}

			return (Int32)bestGuess;
		}

		/// <summary>
		/// Get the integral value of the Fraction object as long/Int64
		/// </summary>
		/// <returns>The (approximate) integer value</returns>
		/// <remarks>If the value is not a true integer, the fractional part is discarded
		/// (truncated toward zero). If the valid exceeds the range of an Int32, no special
		/// handling is guaranteed.</remarks>
		/// <exception cref="FractionException">Will throw a FractionException for NaN, PositiveInfinity
		/// or NegativeInfinity with the InnerException set to a System.NotFiniteNumberException.</exception>
		public Int64 ToInt64()
		{
			if (this.m_Denominator == 0)
			{
				throw new FractionException(string.Format("Cannot convert {0} to Int64", IndeterminateTypeName(this.m_Numerator)), new System.NotFiniteNumberException());
			}

			return this.m_Numerator / this.m_Denominator;
		}

		/// <summary>
		/// Get the value of the Fraction object as double with full support for NaNs and infinities
		/// </summary>
		/// <returns>The decimal representation of the Fraction, or double.NaN, double.NegativeInfinity
		/// or double.PositiveInfinity</returns>
		public double ToDouble()
		{
			if (this.m_Denominator == 1)
				return this.m_Numerator;
			else if (this.m_Denominator == 0)
			{
				switch (NormalizeIndeterminate(this.m_Numerator))
				{
					case Indeterminates.NegativeInfinity:
						return double.NegativeInfinity;

					case Indeterminates.PositiveInfinity:
						return double.PositiveInfinity;

					case Indeterminates.NaN:
					default:    // this can't happen
						return double.NaN;
				}
			}
			else
			{
				return (double)this.m_Numerator / (double)this.m_Denominator;
			}
		}

		/// <summary>
		/// Get the value of the Fraction as a string, with proper representation for NaNs and infinites
		/// </summary>
		/// <returns>The string representation of the Fraction, or the culture-specific representations of
		/// NaN, PositiveInfinity or NegativeInfinity.</returns>
		/// <remarks>The current culture determines the textual representation the Indeterminates</remarks>
		public override string ToString()
		{
			if (this.m_Denominator == 1)
			{
				return this.m_Numerator.ToString();
			}
			else if (this.m_Denominator == 0)
			{
				return IndeterminateTypeName(this.m_Numerator);
			}
			else
			{
				return this.m_Numerator.ToString() + "/" + this.m_Denominator.ToString();
			}
		}
		#endregion

		#region From primitives
		/// <summary>
		/// Converts a long value to the exact Fraction
		/// </summary>
		/// <param name="inValue">The long to convert</param>
		/// <returns>An exact representation of the value</returns>
		public static Fraction ToFraction(long inValue)
		{
			return new Fraction(inValue);
		}

		/// <summary>
		/// Converts a double value to the approximate Fraction
		/// </summary>
		/// <param name="inValue">The double to convert</param>
		/// <returns>A best-fit representation of the value</returns>
		/// <remarks>Supports double.NaN, double.PositiveInfinity and double.NegativeInfinity</remarks>
		public static Fraction ToFraction(double inValue)
		{
			// it's one of the indeterminates... which?
			if (double.IsNaN(inValue))
				return NaN;
			else if (double.IsNegativeInfinity(inValue))
				return NegativeInfinity;
			else if (double.IsPositiveInfinity(inValue))
				return PositiveInfinity;
			else if (inValue == 0.0d)
				return Zero;

			if (inValue > Int64.MaxValue)
				throw new OverflowException(string.Format("Double {0} too large", inValue));

			if (inValue < -Int64.MaxValue)
				throw new OverflowException(string.Format("Double {0} too small", inValue));

			if (-EpsilonDouble < inValue && inValue < EpsilonDouble)
				throw new ArithmeticException(string.Format("Double {0} cannot be represented", inValue));

			int sign = Math.Sign(inValue);
			inValue = Math.Abs(inValue);

			return ConvertPositiveDouble(sign, inValue);
		}

		/// <summary>
		/// Converts a string to the corresponding reduced fraction
		/// </summary>
		/// <param name="inValue">The string representation of a fractional value</param>
		/// <returns>The Fraction that represents the string</returns>
		/// <remarks>Four forms are supported, as a plain integer, as a double, or as Numerator/Denominator
		/// and the representations for NaN and the infinites</remarks>
		/// <example>"123" = 123/1 and "1.25" = 5/4 and "10/36" = 5/13 and NaN = 0/0 and
		/// PositiveInfinity = 1/0 and NegativeInfinity = -1/0</example>
		public static Fraction ToFraction(string inValue)
		{
			if (inValue == null || inValue == string.Empty)
				throw new ArgumentNullException("inValue");

			// could also be NumberFormatInfo.InvariantInfo
			NumberFormatInfo info = NumberFormatInfo.CurrentInfo;

			// Is it one of the special symbols for NaN and such...
			string trimmedValue = inValue.Trim();

			if (trimmedValue == info.NaNSymbol)
				return NaN;
			else if (trimmedValue == info.PositiveInfinitySymbol)
				return PositiveInfinity;
			else if (trimmedValue == info.NegativeInfinitySymbol)
				return NegativeInfinity;
			else
			{
				// Not special, is it a Fraction?
				int slashPos = inValue.IndexOf('/');

				if (slashPos > -1)
				{
					// string is in the form of Numerator/Denominator
					long numerator = Convert.ToInt64(inValue.Substring(0, slashPos));
					long denominator = Convert.ToInt64(inValue.Substring(slashPos + 1));

					return new Fraction(numerator, denominator);
				}
				else
				{
					// the string is not in the form of a fraction
					// hopefully it is double or integer, do we see a decimal point?
					int decimalPos = inValue.IndexOf(info.CurrencyDecimalSeparator);

					if (decimalPos > -1)
						return new Fraction(Convert.ToDouble(inValue));
					else
						return new Fraction(Convert.ToInt64(inValue));
				}
			}
		}
		#endregion
		#endregion

		#region Indeterminate classifications
		/// <summary>
		/// Determines if a Fraction represents a Not-a-Number
		/// </summary>
		/// <returns>True if the Fraction is a NaN</returns>
		public bool IsNaN()
		{
			if (this.m_Denominator == 0 
				&& NormalizeIndeterminate(this.m_Numerator) == Indeterminates.NaN)
				return true;
			else
				return false;
		}

		/// <summary>
		/// Determines if a Fraction represents Any Infinity
		/// </summary>
		/// <returns>True if the Fraction is Positive Infinity or Negative Infinity</returns>
		public bool IsInfinity()
		{
			if (this.m_Denominator == 0
				&& NormalizeIndeterminate(this.m_Numerator) != Indeterminates.NaN)
				return true;
			else
				return false;
		}

		/// <summary>
		/// Determines if a Fraction represents Positive Infinity
		/// </summary>
		/// <returns>True if the Fraction is Positive Infinity</returns>
		public bool IsPositiveInfinity()
		{
			if (this.m_Denominator == 0
				&& NormalizeIndeterminate(this.m_Numerator) == Indeterminates.PositiveInfinity)
				return true;
			else
				return false;
		}

		/// <summary>
		/// Determines if a Fraction represents Negative Infinity
		/// </summary>
		/// <returns>True if the Fraction is Negative Infinity</returns>
		public bool IsNegativeInfinity()
		{
			if (this.m_Denominator == 0
				&& NormalizeIndeterminate(this.m_Numerator) == Indeterminates.NegativeInfinity)
				return true;
			else
				return false;
		}
		#endregion

		#region Inversion
		/// <summary>
		/// Inverts a Fraction
		/// </summary>
		/// <returns>The inverted Fraction (with Denominator over Numerator)</returns>
		/// <remarks>Does NOT throw for zero Numerators as later use of the fraction will catch the error.</remarks>
		public Fraction Inverse()
		{
			// don't use the obvious constructor because we do not want it normalized at this time
			Fraction frac = new Fraction();

			frac.m_Numerator = this.m_Denominator;
			frac.m_Denominator = this.m_Numerator;
			return frac;
		}

		/// <summary>
		/// Creates an inverted Fraction
		/// </summary>
		/// <returns>The inverted Fraction (with Denominator over Numerator)</returns>
		/// <remarks>Does NOT throw for zero Numerators as later use of the fraction will catch the error.</remarks>
		public static Fraction Inverted(long value)
		{
			Fraction frac = new Fraction(value);
			return frac.Inverse();
		}

		/// <summary>
		/// Creates an inverted Fraction
		/// </summary>
		/// <returns>The inverted Fraction (with Denominator over Numerator)</returns>
		/// <remarks>Does NOT throw for zero Numerators as later use of the fraction will catch the error.</remarks>
		public static Fraction Inverted(double value)
		{
			Fraction frac = new Fraction(value);
			return frac.Inverse();
		}
		#endregion

		#region Operators
		#region Unary Negation operator
		/// <summary>
		/// Negates the Fraction
		/// </summary>
		/// <param name="left">The Fraction to negate</param>
		/// <returns>The negative version of the Fraction</returns>
		public static Fraction operator -(Fraction left)
		{
			return Negate(left);
		}
		#endregion

		#region Addition operators
		public static Fraction operator +(Fraction left, Fraction right)
		{
			return Add(left, right);
		}
	    
		public static Fraction operator +(long left, Fraction right)
		{
			return Add(new Fraction(left), right);
		}
	    
		public static Fraction operator +(Fraction left, long right)
		{
			return Add(left, new Fraction(right));
		}

		public static Fraction operator +(double left, Fraction right)
		{
			return Add(ToFraction(left), right);
		}
	    
		public static Fraction operator +(Fraction left, double right)
		{
			return Add(left, ToFraction(right));
		}
		#endregion

		#region Subtraction operators
		public static Fraction operator -(Fraction left, Fraction right)
		{
			return Add(left, - right);
		}
	    
		public static Fraction operator -(long left, Fraction right)
		{
			return Add(new Fraction(left), - right);
		}
	    
		public static Fraction operator -(Fraction left, long right)
		{
			return Add(left, new Fraction(- right));
		}

		public static Fraction operator -(double left, Fraction right)
		{
			return Add(ToFraction(left), - right);
		}
	    
		public static Fraction operator -(Fraction left, double right)
		{
			return Add(left, ToFraction(- right));
		}
		#endregion

		#region Multiplication operators
		public static Fraction operator *(Fraction left, Fraction right)
		{
			return Multiply(left, right);
		}
	    
		public static Fraction operator *(long left, Fraction right)
		{
			return Multiply(new Fraction(left), right);
		}
	    
		public static Fraction operator *(Fraction left, long right)
		{
			return Multiply(left, new Fraction(right));
		}
	    
		public static Fraction operator *(double left, Fraction right)
		{
			return Multiply(ToFraction(left), right);
		}
	    
		public static Fraction operator *(Fraction left, double right)
		{
			return Multiply(left, ToFraction(right));
		}
		#endregion

		#region Division operators
		public static Fraction operator /(Fraction left, Fraction right)
		{
			return Multiply(left, right.Inverse());
		}
	    
		public static Fraction operator /(long left, Fraction right)
		{
			return Multiply(new Fraction(left), right.Inverse());
		}
	    
		public static Fraction operator /(Fraction left, long right)
		{
			return Multiply(left, Inverted(right));
		}
	    
		public static Fraction operator /(double left, Fraction right)
		{
			return Multiply(ToFraction(left), right.Inverse());
		}
	    
		public static Fraction operator /(Fraction left, double right)
		{
			return Multiply(left, Inverted(right));
		}
		#endregion

		#region Modulus operators
		public static Fraction operator %(Fraction left, Fraction right)
		{
			return Modulus(left, right);
		}
	    
		public static Fraction operator %(long left, Fraction right)
		{
			return Modulus(new Fraction(left), right);
		}
	    
		public static Fraction operator %(Fraction left, long right)
		{
			return Modulus(left, right);
		}
	    
		public static Fraction operator %(double left, Fraction right)
		{
			return Modulus(ToFraction(left), right);
		}
	    
		public static Fraction operator %(Fraction left, double right)
		{
			return Modulus(left, right);
		}
		#endregion

		#region Equal operators
		public static bool operator ==(Fraction left, Fraction right)
		{
			return left.CompareEquality(right, false);
		}

		public static bool operator ==(Fraction left, long right)
		{
			return left.CompareEquality(new Fraction(right), false);
		}

		public static bool operator ==(Fraction left, double right)
		{
			return left.CompareEquality(new Fraction(right), false);
		}
		#endregion

		#region Not-equal operators
		public static bool operator !=(Fraction left, Fraction right)
		{
			return left.CompareEquality(right, true);
		}

		public static bool operator !=(Fraction left, long right)
		{
			return left.CompareEquality(new Fraction(right), true);
		}
	        
		public static bool operator !=(Fraction left, double right)
		{
			return left.CompareEquality(new Fraction(right), true);
		}
		#endregion

		#region Inequality operators
		/// <summary>
		/// Compares two Fractions to see if left is less than right
		/// </summary>
		/// <param name="left">The first Fraction</param>
		/// <param name="right">The second Fraction</param>
		/// <returns>True if <paramref name="left">left</paramref> is less
		/// than <paramref name="right">right</paramref></returns>
		/// <remarks>Special handling for indeterminates exists. <see>IndeterminateLess</see></remarks>
		/// <exception cref="FractionException">Throws an error if overflows occur while computing the 
		/// difference with an InnerException of OverflowException</exception>
		public static bool operator <(Fraction left, Fraction right)
		{
			return left.CompareTo(right) < 0;
		}

		/// <summary>
		/// Compares two Fractions to see if left is greater than right
		/// </summary>
		/// <param name="left">The first Fraction</param>
		/// <param name="right">The second Fraction</param>
		/// <returns>True if <paramref name="left">left</paramref> is greater
		/// than <paramref name="right">right</paramref></returns>
		/// <remarks>Special handling for indeterminates exists. <see>IndeterminateLess</see></remarks>
		/// <exception cref="FractionException">Throws an error if overflows occur while computing the 
		/// difference with an InnerException of OverflowException</exception>
		public static bool operator >(Fraction left, Fraction right)
		{
			return left.CompareTo(right) > 0;
		}

		/// <summary>
		/// Compares two Fractions to see if left is less than or equal to right
		/// </summary>
		/// <param name="left">The first Fraction</param>
		/// <param name="right">The second Fraction</param>
		/// <returns>True if <paramref name="left">left</paramref> is less than or 
		/// equal to <paramref name="right">right</paramref></returns>
		/// <remarks>Special handling for indeterminates exists. <see>IndeterminateLessEqual</see></remarks>
		/// <exception cref="FractionException">Throws an error if overflows occur while computing the 
		/// difference with an InnerException of OverflowException</exception>
		public static bool operator <=(Fraction left, Fraction right)
		{
			return left.CompareTo(right) <= 0;
		}
	        
		/// <summary>
		/// Compares two Fractions to see if left is greater than or equal to right
		/// </summary>
		/// <param name="left">The first Fraction</param>
		/// <param name="right">The second Fraction</param>
		/// <returns>True if <paramref name="left">left</paramref> is greater than or 
		/// equal to <paramref name="right">right</paramref></returns>
		/// <remarks>Special handling for indeterminates exists. <see>IndeterminateLessEqual</see></remarks>
		/// <exception cref="FractionException">Throws an error if overflows occur while computing the 
		/// difference with an InnerException of OverflowException</exception>
		public static bool operator >=(Fraction left, Fraction right)
		{
			return left.CompareTo(right) >= 0;
		}
		#endregion

		#region Implict conversion from primitive operators
		/// <summary>
		/// Implicit conversion of a long integral value to a Fraction
		/// </summary>
		/// <param name="value">The long integral value to convert</param>
		/// <returns>A Fraction whose denominator is 1</returns>
		public static implicit operator Fraction(long value)
		{
			return new Fraction(value);
		}

		/// <summary>
		/// Implicit conversion of a double floating point value to a Fraction
		/// </summary>
		/// <param name="value">The double value to convert</param>
		/// <returns>A reduced Fraction</returns>
		public static implicit operator Fraction(double value)
		{
			return new Fraction(value);
		}

		/// <summary>
		/// Implicit conversion of a string to a Fraction
		/// </summary>
		/// <param name="value">The string to convert</param>
		/// <returns>A reduced Fraction</returns>
		public static implicit operator Fraction(string value)
		{
			return new Fraction(value);
		}
		#endregion

		#region Explicit converstion to primitive operators
		/// <summary>
		/// Explicit conversion from a Fraction to an integer
		/// </summary>
		/// <param name="frac">the Fraction to convert</param>
		/// <returns>The integral representation of the Fraction</returns>
		public static explicit operator int(Fraction frac)
		{
			return frac.ToInt32();
		}

		/// <summary>
		/// Explicit conversion from a Fraction to an integer
		/// </summary>
		/// <param name="frac">The Fraction to convert</param>
		/// <returns>The integral representation of the Fraction</returns>
		public static explicit operator long(Fraction frac)
		{
			return frac.ToInt64();
		}

		/// <summary>
		/// Explicit conversion from a Fraction to a double floating-point value
		/// </summary>
		/// <param name="frac">The Fraction to convert</param>
		/// <returns>The double representation of the Fraction</returns>
		public static explicit operator double(Fraction frac)
		{
			return frac.ToDouble();
		}

		/// <summary>
		/// Explicit conversion from a Fraction to a string
		/// </summary>
		/// <param name="frac">the Fraction to convert</param>
		/// <returns>The string representation of the Fraction</returns>
		public static implicit operator string(Fraction frac)
		{
			return frac.ToString();
		}
		#endregion
		#endregion

		#region Equals and GetHashCode overrides
		/// <summary>
		/// Compares for equality the current Fraction to the value passed.
		/// </summary>
		/// <param name="obj">A  Fraction,</param>
		/// <returns>True if the value equals the current fraction, false otherwise (including for
		/// non-Fraction types or null object.</returns>
		public override bool Equals(object obj)
		{
			if (obj == null	|| ! (obj is Fraction))
				return false;

			try 
			{
				Fraction right = (Fraction)obj;
				return this.CompareEquality(right, false);
			}
			catch
			{
				// can't throw in an Equals!
				return false;
			}
		}
	        
		/// <summary>
		/// Returns a hash code generated from the current Fraction
		/// </summary>
		/// <returns>The hash code</returns>
		/// <remarks>Reduces (in-place) the Fraction first.</remarks>
		public override int GetHashCode()
		{
			// insure we're as close to normalized as possible first
			ReduceFraction(ref this);

			int numeratorHash = this.m_Numerator.GetHashCode();
			int denominatorHash = this.m_Denominator.GetHashCode();

			return (numeratorHash ^ denominatorHash);
		}
		#endregion

		#region IComparable member and type-specific version
		/// <summary>
		/// Compares an object to this Fraction
		/// </summary>
		/// <param name="obj">The object to compare against (null is less than everything)</param>
		/// <returns>-1 if this is less than <paramref name="obj"></paramref>,
		///  0 if they are equal,
		///  1 if this is greater than <paramref name="obj"></paramref></returns>
		/// <remarks>Will convert an object from longs, doubles, and strings as this is a value-type.</remarks>
		public int CompareTo(object obj)
		{
			if (obj == null)
				return 1;	// null is less than anything

			Fraction right;

			if (obj is Fraction)
				right = (Fraction)obj;
			else if (obj is long)
				right = (long)obj;
			else if (obj is double)
				right = (double)obj;
			else if (obj is string)
				right = (string)obj;
			else
				throw new ArgumentException("Must be convertible to Fraction", "obj");

			return this.CompareTo(right);
		}

		/// <summary>
		/// Compares this Fraction to another Fraction
		/// </summary>
		/// <param name="right">The Fraction to compare against</param>
		/// <returns>-1 if this is less than <paramref name="right"></paramref>,
		///  0 if they are equal,
		///  1 if this is greater than <paramref name="right"></paramref></returns>
		public int CompareTo(Fraction right)
		{
			// if left is an indeterminate, punt to the helper...
			if (this.m_Denominator == 0)
			{
				return IndeterminantCompare(NormalizeIndeterminate(this.m_Numerator), right);
			}

			// if right is an indeterminate, punt to the helper...
			if (right.m_Denominator == 0)
			{
				// note sign-flip...
				return - IndeterminantCompare(NormalizeIndeterminate(right.m_Numerator), this);
			}

			// they're both normal Fractions
			CrossReducePair(ref this, ref right);

			try
			{
				checked
				{
					long leftScale = this.m_Numerator * right.m_Denominator;
					long rightScale = this.m_Denominator * right.m_Numerator;

					if (leftScale < rightScale)
						return -1;
					else if (leftScale > rightScale)
						return 1;
					else
						return 0;
				}
			}
			catch (Exception e)
			{
				throw new FractionException(string.Format("CompareTo({0}, {1}) error", this, right), e);
			}
		}
		#endregion

		#region IFormattable Members
		string System.IFormattable.ToString(string format, IFormatProvider formatProvider)
		{
			return this.m_Numerator.ToString(format, formatProvider) + "/" + this.m_Denominator.ToString(format, formatProvider);
		}
		#endregion

		#region Reduction
		/// <summary>
		/// Reduces (simplifies) a Fraction by dividing down to lowest possible denominator (via GCD)
		/// </summary>
		/// <param name="frac">The Fraction to be reduced [WILL BE MODIFIED IN PLACE]</param>
		/// <remarks>Modifies the input arguments in-place! Will normalize the NaN and infinites
		/// representation. Will set Denominator to 1 for any zero numerator. Moves sign to the
		/// Numerator.</remarks>
		/// <example>2/4 will be reduced to 1/2</example>
		public static void ReduceFraction(ref Fraction frac)
		{
			// clean up the NaNs and infinites
			if (frac.m_Denominator == 0)
			{
				frac.m_Numerator = (long)NormalizeIndeterminate(frac.m_Numerator);
				return;
			}

			// all forms of zero are alike.
			if (frac.m_Numerator == 0)
			{
				frac.m_Denominator = 1;
				return;
			}
	            
			long iGCD = GCD(frac.m_Numerator, frac.m_Denominator);
			frac.m_Numerator /= iGCD;
			frac.m_Denominator /= iGCD;
	        
			// if negative sign in denominator
			if ( frac.m_Denominator < 0 )
			{
				//move negative sign to numerator
				frac.m_Numerator = - frac.m_Numerator;
				frac.m_Denominator = - frac.m_Denominator;  
			}
		}

		/// <summary>
		/// Cross-reduces a pair of Fractions so that we have the best GCD-reduced values for multiplication
		/// </summary>
		/// <param name="frac1">The first Fraction [WILL BE MODIFIED IN PLACE]</param>
		/// <param name="frac2">The second Fraction [WILL BE MODIFIED IN PLACE]</param>
		/// <remarks>Modifies the input arguments in-place!</remarks>
		/// <example>(3/4, 5/9) = (1/4, 5/3)</example>
		public static void CrossReducePair(ref Fraction frac1, ref Fraction frac2)
		{
			// leave the indeterminates alone!
			if (frac1.m_Denominator == 0 || frac2.m_Denominator == 0)
				return;

			long gcdTop = GCD(frac1.m_Numerator, frac2.m_Denominator);
			frac1.m_Numerator = frac1.m_Numerator / gcdTop;
			frac2.m_Denominator = frac2.m_Denominator / gcdTop;

			long gcdBottom = GCD(frac1.m_Denominator, frac2.m_Numerator);
			frac2.m_Numerator = frac2.m_Numerator / gcdBottom;
			frac1.m_Denominator = frac1.m_Denominator / gcdBottom;
		}
		#endregion

		#region Implementation
		#region Convert a double to a fraction
		private static Fraction ConvertPositiveDouble(int sign, double inValue)
		{
			// Shamelessly stolen from http://homepage.smc.edu/kennedy_john/CONFRAC.PDF
			// with AccuracyFactor == double.Episilon
			long fractionNumerator = (long)inValue;
			double fractionDenominator = 1;
			double previousDenominator = 0;
			double remainingDigits = inValue;
			int maxIterations = 594;	// found at http://www.ozgrid.com/forum/archive/index.php/t-22530.html

			while (remainingDigits != Math.Floor(remainingDigits) 
				&& Math.Abs(inValue - (fractionNumerator / fractionDenominator)) > double.Epsilon)
			{
				remainingDigits = 1.0 / (remainingDigits - Math.Floor(remainingDigits));

				double scratch = fractionDenominator;

				fractionDenominator =(Math.Floor(remainingDigits) * fractionDenominator) + previousDenominator;
				fractionNumerator = (long)(inValue * fractionDenominator + 0.5);

				previousDenominator = scratch;

				if (maxIterations-- < 0)
					break;
			}

			return new Fraction(fractionNumerator * sign, (long)fractionDenominator);
		}
		#endregion

		#region Equality helper
		/// <summary>
		/// Compares for equality the current Fraction to the value passed.
		/// </summary>
		/// <param name="right">A Fraction to compare against</param>
		/// <param name="notEqualCheck">If true, we're looking for not-equal</param>
		/// <returns>True if the <paramref name="right"></paramref> equals the current 
		/// fraction, false otherwise. If comparing two NaNs, they are always equal AND
		/// not-equal.</returns>
		private bool CompareEquality(Fraction right, bool notEqualCheck)
		{
			// insure we're normalized first
			ReduceFraction(ref this);

			// now normalize the comperand
			ReduceFraction(ref right);

			if (this.m_Numerator == right.m_Numerator && this.m_Denominator == right.m_Denominator)
			{
				// special-case rule, two NaNs are always both equal
				if (notEqualCheck && this.IsNaN())
					return true;
				else
					return ! notEqualCheck;
			}
			else
			{
				return notEqualCheck;
			}
		}
		#endregion

		#region Comparison helper
		/// <summary>
		/// Determines how this Fraction, of an indeterminate type, compares to another Fraction
		/// </summary>
		/// <param name="leftType">What kind of indeterminate</param>
		/// <param name="right">The other Fraction to compare against</param>
		/// <returns>-1 if this is less than <paramref name="right"></paramref>,
		///  0 if they are equal,
		///  1 if this is greater than <paramref name="right"></paramref></returns>
		/// <remarks>NaN is less than anything except NaN and Negative Infinity. Negative Infinity is less
		/// than anything except Negative Infinity. Positive Infinity is greater than anything except
		/// Positive Infinity.</remarks>
		private static int IndeterminantCompare(Indeterminates leftType, Fraction right)
		{
			switch (leftType)
			{
				case Indeterminates.NaN:
					// A NaN is...
					if (right.IsNaN())
						return 0;	// equal to a NaN
					else if (right.IsNegativeInfinity())
						return 1;	// great than Negative Infinity
					else
						return -1;	// less than anything else

				case Indeterminates.NegativeInfinity:
					// Negative Infinity is...
					if (right.IsNegativeInfinity())
						return 0;	// equal to Negative Infinity
					else
						return -1;	// less than anything else

				case Indeterminates.PositiveInfinity:
					if (right.IsPositiveInfinity())
						return 0;	// equal to Positive Infinity
					else
						return 1;	// greater than anything else

				default:
					// this CAN'T happen, something VERY wrong is going on...
					return 0;
			}
		}
		#endregion

		#region Math helpers
		/// <summary>
		/// Negates the Fraction
		/// </summary>
		/// <param name="frac">Value to negate</param>
		/// <returns>A new Fraction that is sign-flipped from the input</returns>
		private static Fraction Negate(Fraction frac)
		{
			// for a NaN, it's still a NaN
			return new Fraction( - frac.m_Numerator, frac.m_Denominator);
		}

		/// <summary>
		/// Adds two Fractions
		/// </summary>
		/// <param name="left">A Fraction</param>
		/// <param name="right">Another Fraction</param>
		/// <returns>Sum of the Fractions. Returns NaN if either Fraction is a NaN.</returns>
		/// <exception cref="FractionException">Will throw if an overflow occurs when computing the
		/// GCD-normalized values.</exception>
		private static Fraction Add(Fraction left, Fraction right)
		{
			if (left.IsNaN() || right.IsNaN())
				return NaN;

			long gcd = GCD(left.m_Denominator, right.m_Denominator); // cannot return less than 1
			long leftDenominator = left.m_Denominator / gcd;
			long rightDenominator = right.m_Denominator / gcd;

			try
			{
				checked
				{
					long numerator = left.m_Numerator * rightDenominator + right.m_Numerator * leftDenominator;
					long denominator = leftDenominator * rightDenominator * gcd;

					return new Fraction(numerator, denominator);
				}
			}
			catch (Exception e)
			{
				throw new FractionException("Add error", e);
			}
		}
	    
		/// <summary>
		/// Multiplies two Fractions
		/// </summary>
		/// <param name="left">A Fraction</param>
		/// <param name="right">Another Fraction</param>
		/// <returns>Product of the Fractions. Returns NaN if either Fraction is a NaN.</returns>
		/// <exception cref="FractionException">Will throw if an overflow occurs. Does a cross-reduce to 
		/// insure only the unavoidable overflows occur.</exception>
		private static Fraction Multiply(Fraction left, Fraction right)
		{
			if (left.IsNaN() || right.IsNaN())
				return NaN;

			// this would be unsafe if we were not a ValueType, because we would be changing the
			// caller's values.  If we change back to a class, must use temporaries
			CrossReducePair(ref left, ref right);

			try
			{
				checked
				{
					long numerator = left.m_Numerator * right.m_Numerator;
					long denominator = left.m_Denominator * right.m_Denominator;

					return new Fraction(numerator, denominator);
				}
			}
			catch (Exception e)
			{
				throw new FractionException("Multiply error", e);
			}
		}

		/// <summary>
		/// Returns the modulus (remainder after dividing) two Fractions
		/// </summary>
		/// <param name="left">A Fraction</param>
		/// <param name="right">Another Fraction</param>
		/// <returns>Modulus of the Fractions. Returns NaN if either Fraction is a NaN.</returns>
		/// <exception cref="FractionException">Will throw if an overflow occurs. Does a cross-reduce to 
		/// insure only the unavoidable overflows occur.</exception>
		private static Fraction Modulus(Fraction left, Fraction right)
		{
			if (left.IsNaN() || right.IsNaN())
				return NaN;

			try
			{
				checked
				{
					// this will discard any fractional places...
					Int64 quotient = (Int64)(left / right);
					Fraction whole = new Fraction(quotient * right.m_Numerator, right.m_Denominator);
					return left - whole;
				}
			}
			catch (Exception e)
			{
				throw new FractionException("Modulus error", e);
			}
		}

		/// <summary>
		/// Computes the greatest common divisor for two values
		/// </summary>
		/// <param name="left">One value</param>
		/// <param name="right">Another value</param>
		/// <returns>The greatest common divisor of the two values</returns>
		/// <example>(6, 9) returns 3 and (11, 4) returns 1</example>
		private static long GCD(long left, long right)
		{
			// take absolute values
			if (left < 0)
				left = - left;

			if (right < 0)
				right = - right;
	            
			// if we're dealing with any zero or one, the GCD is 1
			if (left < 2 || right < 2)
				return 1;

			do
			{
				if (left < right)
				{
					long temp = left;  // swap the two operands
					left = right;
					right = temp;
				}

				left %= right;
			} while (left != 0);

			return right;
		}
		#endregion

		#region Indeterminate helpers
		/// <summary>
		/// Gives the culture-related representation of the indeterminate types NaN, PositiveInfinity
		/// and NegativeInfinity
		/// </summary>
		/// <param name="numerator">The value in the numerator</param>
		/// <returns>The culture-specific string representation of the implied value</returns>
		/// <remarks>Only the sign and zero/non-zero information is relevant.</remarks>
		private static string IndeterminateTypeName(long numerator)
		{
			// could also be NumberFormatInfo.InvariantInfo
			System.Globalization.NumberFormatInfo info = NumberFormatInfo.CurrentInfo;

			switch (NormalizeIndeterminate(numerator))
			{
				case Indeterminates.PositiveInfinity:
					return info.PositiveInfinitySymbol;

				case Indeterminates.NegativeInfinity:
					return info.NegativeInfinitySymbol;

				default:    // if this happens, something VERY wrong is going on...
				case Indeterminates.NaN:
					return info.NaNSymbol;
			}
		}

		/// <summary>
		/// Gives the normalize representation of the indeterminate types NaN, PositiveInfinity
		/// and NegativeInfinity
		/// </summary>
		/// <param name="numerator">The value in the numerator</param>
		/// <returns>The normalized version of the indeterminate type</returns>
		/// <remarks>Only the sign and zero/non-zero information is relevant.</remarks>
		private static Indeterminates NormalizeIndeterminate(long numerator)
		{
			switch (Math.Sign(numerator))
			{
				case 1:
					return Indeterminates.PositiveInfinity;

				case -1:
					return Indeterminates.NegativeInfinity;

				default:    // if this happens, your Math.Sign function is BROKEN!
				case 0:
					return Indeterminates.NaN;
			}
		}

		// These are used to represent the indeterminate with a Denominator of zero
		private enum Indeterminates
		{
			NaN = 0
			, PositiveInfinity = 1
			, NegativeInfinity = -1
		}
		#endregion

		#region Member variables
		private long m_Numerator;
		private long m_Denominator;
		#endregion
		#endregion
	}   //end class Fraction

	/// <summary>
	/// Exception class for Fraction, derived from System.Exception
	/// </summary>
	public class FractionException : Exception
	{
		/// <summary>
		/// Constructs a FractionException
		/// </summary>
		/// <param name="Message">String associated with the error message</param>
		/// <param name="InnerException">Actual inner exception caught</param>
		public FractionException(string Message, Exception InnerException) : base(Message, InnerException)
		{
		}
	}   //end class FractionException
}   //end namespace Mehroz
